//
// Created by francklinson on 2021/7/11.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int hIndex(vector<int> &citations) {
        sort(citations.begin(), citations.end());
        int h = 0, i = (int) citations.size() - 1;
        while (i >= 0 and citations[i] > h) {
            ++h;
            --i;
        }
        return h;
    }
};

class Solution2 { // 题解 计数排序
public:
    int hIndex(vector<int> &citations) {
        int n = citations.size(), tot = 0;
        vector<int> counter(n + 1);
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++; // h不可能超过论文总数
            } else {
                counter[citations[i]]++;
            }
        }
        for (int i = n; i >= 0; i--) {
            tot += counter[i];
            if (tot >= i) {
                return i;
            }
        }
        return 0;
    }
};

int main() {
    vector<int> citations{3, 0, 6, 5, 1};
    Solution2 sol;
    cout << sol.hIndex(citations) << endl;
    return 0;
}